package com.lw.leetcode.arr.b;

/**
 * Created with IntelliJ IDEA.
 * 31. 下一个排列
 *
 * @author liw
 * @version 1.0
 * @date 2021/10/13 13:11
 */
public class NextPermutation {

    public void nextPermutation(int[] nums) {
        if (nums == null || nums.length < 2) {
            return;
        }

        int length = nums.length;
        int index = length;
        for (int i = length - 1; i > 0; i--) {
            if (nums[i] > nums[i - 1]) {
                index = i;
                break;
            }
        }
        int st = 0;
        int end = length - 1;
        if (index != length) {
            int max = nums[index];
            int maxIndex = index;
            int value = nums[index - 1];
            for (int i = index; i < length; i++) {
                if (nums[i] > value && nums[i] <= max) {
                    maxIndex = i;
                } else if (nums[i] <= value) {
                    break;
                }
            }
            int item = nums[maxIndex];
            nums[maxIndex] = nums[index - 1];
            nums[index - 1] = item;
            st = index;
            end = length - 1;
        }
        while (st < end) {
            int item = nums[st];
            nums[st] = nums[end];
            nums[end] = item;
            st++;
            end--;
        }
    }
}
